package leecode

func preimageSizeFZF(k int) int {
	return getIndex(k+1) - getIndex(k)
}

func getIndex(k int) int {
	var start, end int = 0, int(5 * k)
	var mid int
	for start <= end {
		mid = (start + end) / 2
		if zeroCount(mid) >= k {
			end = mid - 1
		} else {
			start = mid + 1
		}
	}
	return end + 1
}

// 求对应阶乘后0的个数
func zeroCount(num int) int {
	//0的个数取决于num中有几个 2 , 5的数量 , 5的数量会远小于2
	count := 0
	for i := 5; i <= num; i = i + 5 {
		for x := i; x%5 == 0; x = x / 5 {
			count++
		}
	}
	return count
}
